An outstanding problem in computer science relates to image and data compression. To understand the problem, consider a digitized graytone image, such as a photograph of a natural scene, of size 1024.times.1024. If there are 256 graytone intensities, then the image is completely described by a binary string of 1024.times.1024.times.8 bits. Hence, if no compression is used, more than one megabyte of core memory is required by an computer simply to be able to handle one image. Image compression involves decreasing the length of the binary string in such a way that the exact image can be retrieved. Prior art image compression techniques yield poor results; for typical images of the type just described, compression ratios range between 0.5 and 0.1.
There are four main reasons for desiring effective compression. First, the speed of transmission of a data file is essentially proportional to its size. The larger the file, the longer it takes to transmit. Secondly, the storage space required is proportional to the file size. To keep sixty uncompressed images of the type mentioned above requires sixty megabytes of storage space. If compressed to fifty percent, twice as many images can be kept in the same space. The third reason is that compressed images cost less to transmit, process and store. The fourth reason concerns the rate at which the information can be processed. For example, suppose it is required to compare an image against a library of stored images to detect whether or not a rocket launch event has taken place. The only difference between the images may be in a minute smoke trail--to detect this from uncompressed data, it is necessary to compare the files bit by bit. Alternatively, one may compare the compressed files, at correspondingly greater rates. The point is that all the information is present in the compressed code. For this reason, if no other, data compression is likely to play an important role in knowledge based computing systems.
Many data files contain much redundant information. For example, an image of a natural scene may contain a meadow, trees and sky. Once one knows what a particular blade of grass looks like, one has useful information about the others, so there are enormous amounts of redundant information in a meadow scene. The pine needles on a pine tree are by no means randomly placed in the image; they are organized by the underlying structure of the tree. The structures of the clouds are governed to good approximation by briefly expressed equations of physics, such as the Navier-Stokes equations. These statements are not meant to imply how compression is to be achieved, but to argue that it is possible.
The need for compression increases in significance when data files describing three, four, and five dimensional scenes are considered. Vast data bases currently need to be accessed and processed in real time in flight simulators and in autonomous flying craft. Topographical data together with reflectance, radar and microwave characteristics, for significant areas of the North American continent must be utilized in simulators. Similar data sets need to be resident in machine intelligent low-flying craft. In these circumstances, not only do the required data files increase in size by orders of magnitude, but also the proportion of redundancy in the information increases, meaning that improved compression ratios should be achievable.
In the present state of the art in computer graphics, there are many problems in representing real-world images in forms for computer based storage, transmission or communications, and analysis. For example, although the details in a mountain landscape are easily captured in a photograph, a computer re-creation would normally require a complicated program or the storage of millions of bits of data. Efficient compression schemes could result in more effective means for storing data in a computer's memory, for transmitting photographs over telephone lines, for recognizing specific objects in a landscape, and for simulating natural scenery on a computer.
Paradoxically, the continuing improvements in computer graphic hardware and software only compound the problems encountered. Faster hardware for computer graphics increases the rate of graphic production and thus increases demand on transmission or storage. The quest for realism drives graphics software to produce images of increasing complexity. Increasing image complexity means more information must be transmitted or stored for each image. Sophisticated printers also increase transmission and storage requirements. Recently available color printers are a case in point. Producing an 81/2" by 11" color printout at 300 dots per inch resolution and 24 bits per dot can consume over 20 megabits of data. Even at the ISDN (Integrated Services Digital Network) bandwidth of 64,000 bits per second, it will take over five minutes to supply the necessary data to drive the printer.
Accordingly, there is a clear need for an efficient and effective method and apparatus for compressing high resolution image data for storage or communications.
As is known to those skilled in the art, digital data compression consists of encoding and decoding phases. In the encoding phase, an input string of I bits is transformed into a coded string of C bits. The ratio I:C is the compression ratio. In the decoding phase the compressed string regenerates the original data. If the compression ratio is 2:1 then in the time it takes to transmit one uncompressed image, two compressed images may be transmitted.
In the prior art, there are several major classes of image compression techniques including transform and predictive types. The International Standards Organization (ISO) and the International Telegraph and Telephone Consultative Committee (ITTCC) are considering the establishment of international standards for image compression. Basically, the compression ratios under consideration are relatively low for exact image reproduction. For example, one exact compression technique recently discussed calls for a compression ratio of 2:1. Exact compression requires that the decoded image is identical to the original image which was encoded. There are several common exact techniques. They are not particularly useful for highly compressing realistic images. In one experiment, a photo montage was run-length encoded and actually produced a 60% increase in data length over the original input file size instead of a compression. The UNIX computer operating system provides a Huffman encoder which yields a compression ratio of 10:9. A Ziv-Lempel Compress algorithm has yielded a 5:4 compression ratio for image data. Such ratios are common for exact techniques. Plainly, it has proven difficult for those skilled in the art to compress images exactly with satisfactory results.
Other prior art image compression nonexact techniques include a General Electric image compression system, originally developed at the Sarnoff Research Center, which has produced 30:1 compression ratios on still video and 100:1 compression ratios on motion video. This technique is not an exact technique at those ratios and introduces artifacts in the decoded reproduction of the original image.
Most known compression techniques work best within certain classes of images. One familiar example is the normal ASCII encoding of a page of text. Transmitting the symbols rather than a bit map of the page of text can provide a compression ratio exceeding 1000:1. It is a goal of computer development to make graphics as easy to transmit as text.
It is believed by the inventors that the key to image compression is in the redundancy found in images of natural scenes. As mentioned earlier, one pine needle in an image of a forest is more or less like any other pine needle in that image. A compressed image does not require description of each pine needle in the image; rather, a single pine needle is described and then its basic information is utilized via mathematical algorithms to reproduced other pine needles in the image in a natural manner.
Furthermore, nature is full of shapes that repeat themselves on different scales within the same object. A fragment of rock looks like the mountain from which it was fractured. Clouds keep their distinctive appearance whether viewed from the ground or from an airplane window. A tree's twigs may have the same branching pattern seen at the tree's trunk.
In all these examples, zooming in for a closer view does not smooth out the irregularities. Instead, the objects tend to show the same degree of roughness or branching at different levels of magnification. In 1975, Benoit B. Mandelbrot coined the word "fractal" to describe such irregular and fragmented shapes, which can be magnified endlessly and still retain their complicated structure.
Fractal geometry is an extension of classical (Euclidean) geometry. The areas of application and the diverse different ways in which the subject is developed and applied in science and in engineering can be envisaged when one thinks of how much of present technology is based on the use of classical geometry. For example, calculus is based on the use of straight lines when functions are magnified sufficiently, linear models for diverse phenomena in diverse areas are in vastly predominant use, straight edges and compasses are used for drawing straight lines and circles, polygonal representations of objects are used for image generation in computer graphics, and so on.
Fractal geometry is therefore a new focus for theoretical and practical research. As to what the body of knowledge which we might now want to call "fractal geometry" will look like in the future is not clear: the area is currently very active, and there are many diverse branches of study involving fractal themes in one way or another. The important point is that fractal geometry is a very diverse and yound field, and there are many different directions being taken in attempting to develop practical uses for the geometry. The area is conceivably as broad as "mechanics" or "biology". Merely because the term "fractal" appears in certain applications does not mean that the particular "fractal" techniques referred to are in any technical way related to other "fractal" techniques referred to in other applications.
The mathematics of fractals has been used to create images that look a lot like clouds, mountains and other forms. Usually, the process involves providing a computer with a small set of numbers that generates a basic shape, such as a triangle. That shape is then recreated many times on smaller and smaller scales within the original figure. Random variations are introduced to make the image look a little rougher and therefore more realistic. Such artificial landscapes can be mathematically magnified to reveal more detail, just as a close-up lens probes deeply into a natural scene. These random recursive refinement techniques of image production are totally unrelated to the techniques claimed by the inventors in this patent application.
These other fractal techniques do not achieve image compression for the following reason. In order to store any image created by one of these fractal modelling techniques it is necessary to specify a particular long sequence of numbers which specify the random variations that were used in the encoding process. To tell a computer how to recreate the image exactly, one must specify all of the random numbers which were used in the generation of the image. Furthermore, they do not in general correspond to real-world images. They are typically the result of research and experimentation with mathematical procedures (or algorithms) that happen to lead to drawings that look like natural objects. This approach is therefore not an "exact image" encoding method, since it starts with a mathematical description and results in something that looks real, but does not look like any particular real thing. There is therefore still a great need in the art of computer graphics and fractal geometry to be able to represent real-world images with fractal geometric representations.